let isqrt n = int_of_float (sqrt (Int64.to_float n));;

type status = Unknown | Prime | Composed;;

let rec make_nat_list n l =
   match n with
     0 -> l
   | _ -> make_nat_list (n-1) ([(n,Unknown)]@l);;

let nat_list n = make_nat_list n [];;

let rec sieve nmax l =
   (* let p = try
      fst (List.find (fun y -> if (snd y = Unknown) then true else false) l)
   with Not_found -> fst (List.hd l) in *)
   let p = 
      fst (List.find (fun y -> if (snd y = Unknown) then true else false) l) in
   if ( p > nmax ) then l
   else
      let f (x,tag) = 
         if ( x = p ) then 
            (x,Prime)
         else 
            if ( (x mod p) <> 0 ) then 
               (x,tag) 
            else (x,Composed) 
      in
      sieve nmax (List.map f l);;

let primes_list valmax =
   let sqmax = isqrt (Int64.of_int valmax) in
   (* let sqmax = valmax in *)
   let nats_from_2 = List.tl (nat_list valmax) in
   let l = sieve sqmax nats_from_2 in
   let lprimes = 
      List.filter (fun x -> match (snd x) with Prime -> true | _ -> false) l
   in List.map (fun x -> (fst x)) lprimes;;

primes_list 2000;;

let n = Int64.of_string "13195" in
let sq_n = isqrt n in
;;

let n = Int64.of_string "600851475143" in
isqrt n;;
